home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / COMAL / Z-Misc Series / (k)zd.d64 / txt.sets < prev   
Text File  |  2007-03-01  |  6KB  |  291 lines

  1. ╙┼╘╙ ╔╬ ├╧═┴╠
  2.  
  3. BY ─ICK ╦LINGENS, ─UTCH ├╧═┴╠ ╒SERS
  4. ╟ROUP
  5.  
  6.  
  7. ╔N MATHEMATICS SETS ARE USED TO SOLVE
  8. CERTAIN DISCRETE PROBLEMS. ╔N SOME
  9. PROGRAMMING LANGUAGES (╨ASCAL, ┴─┴)
  10. SETS ARE IMPLEMENTED TO DEAL WITH
  11. SUCH PROBLEMS. ╔T IS POSSIBLE TO
  12. CREATE SETS IN ├╧═┴╠ IN AN EASY WAY.
  13. ╔F AN ELEMENT IS A MEMBER OF A SET
  14. (IS IN A SET), WE CAN RECORD THAT
  15. WITH ╘╥╒┼ (ONE BIT); IF NOT WITH
  16. ╞┴╠╙┼. ╞OR 30 ELEMENTS WE NEED A
  17. SEQUENCE OF 30 BITS, ONE FOR EACH
  18. ELEMENT.
  19.  
  20. ┼XAMPLE.
  21.  
  22.         111111
  23. 12345678012345 <- ELEMENTS
  24. --------------
  25. 00100000011100 <- BIT REPRESENTATION
  26.                   OF THE SET
  27.  
  28. ╫E HAVE A SET WITH ELEMENTS
  29.     3, 11, 12, 13, ...
  30.  
  31. ╙UCH A BIT SEQUENCE CAN BE
  32. REPRESENTED BY A REAL NUMBER: A SET
  33. IS A REAL NUMBER. ╔N THE FOLLOWING WE
  34. SHALL CREATE SETS WITH A MAXIMUM OF
  35. 30 ELEMENTS.
  36.  
  37. ╫E NEED TWO FUNCTIONS; THE FIRST TO
  38. TRANSFER A SET INTO A SEQUENCE OF
  39. BITS (ONE'S AND ZERO'S IN A STRING)
  40. AND THE SECOND TO TRANSFER A BIT
  41. SEQUENCE INTO A SET.
  42.  
  43. // FROM SET TO BITS
  44. ╞╒╬├ BSTR$(NUMBER) ├╠╧╙┼─
  45.   ─╔═ BINAR$ ╧╞ 30
  46.   BINAR$:=BIN$(NUMBER) // CONVERSION
  47.   ╫╚╔╠┼ ╠┼╬(BINAR$)<30 ─╧
  48.     // ADD LEADING ZERO'S
  49.     BINAR$:="0"+BINAR$
  50.   ┼╬─╫╚╔╠┼
  51.   ╥┼╘╒╥╬ BINAR$
  52.   //
  53.   ╞╒╬├ BIN$(NUMBER) ├╠╧╙┼─
  54.     ╔╞ NUMBER=0 ╘╚┼╬
  55.       ╥┼╘╒╥╬ ""
  56.     ┼╠╙┼
  57.       ╥┼╘╒╥╬ BIN$(NUMBER ─╔╓ 2)+
  58.              ╙╘╥$(NUMBER ═╧─ 2)
  59.     ┼╬─╔╞
  60.   ┼╬─╞╒╬├ BIN$
  61. ┼╬─╞╒╬├ BSTR$
  62. //
  63. ╞╒╬├ BVAL(BINAR$) ├╠╧╙┼─
  64.   ╔╞ BINAR$="" ╘╚┼╬
  65.     ╥┼╘╒╥╬ 0
  66.   ┼╠╙┼
  67.     L:=╠┼╬(BINAR$)
  68.     ╥┼╘╒╥╬ BVAL(BINAR$(1:L-1))*2+
  69.            ╓┴╠(BINAR$(L:L))
  70.   ┼╬─╔╞
  71. ┼╬─╞╒╬├ BVAL
  72.  
  73. ╘O CREATE A SET OF ONE ELEMENT WE
  74. HAVE
  75.  
  76. ╞╒╬├ SETOF(ELEMENT) ├╠╧╙┼─
  77.   ╔═╨╧╥╘ BSTR$,BVAL
  78.   ─╔═ BINAR$ ╧╞ 30
  79.   BINAR$:=BSTR$(0) // ONLY ZERO'S
  80.   BINAR$(ELEMENT):="1"
  81.   ╥┼╘╒╥╬ BVAL(BINAR$)
  82. ┼╬─╞╒╬├ SETOF
  83.  
  84. ╒SING THIS FUNCTION:
  85.  
  86.    SET1:=SETOF(2)
  87.    SET2:=SETOF(5)
  88.  
  89. WE HAVE THE SETS
  90.    (2) AND (5)
  91.  
  92. ╫E CAN INCLUDE AN ELEMENT IN A SET BY
  93.  
  94. ╞╒╬├ INCLUDE(SET,ELEMENT) ├╠╧╙┼─
  95.   ╔═╨╧╥╘ BSTR$,BVAL
  96.   ─╔═ BINAR$ ╧╞ 30
  97.   BINAR$:=BSTR$(SET)
  98.   BINAR$(ELEMENT):="1"
  99.   ╥┼╘╒╥╬ BVAL(BINAR$)
  100. ┼╬─╞╒╬├ INCLUDE
  101.  
  102. ┴ND NOW:
  103.    SET1:=INCLUDE(SET1,5)
  104.    SET2:=INCLUDE(INCLUDE(SET2,3),6)
  105.  
  106. ╘HEN THE SETS ARE:
  107.    (2,5) AND (3,5,6)
  108.  
  109. ╫ITH TWO OTHER FUNCTIONS WE CAN USE
  110. THE SET OPERATIONS UNION AND SECTION.
  111.  
  112. ╞╒╬├ UNION(SET1,SET2) ├╠╧╙┼─
  113.   ╔═╨╧╥╘ BSTR$,BVAL
  114.   ─╔═ BINAR1$ ╧╞ 30, BINAR2$ ╧╞ 30
  115.   BINAR1$:=BSTR$(SET1)
  116.   BINAR2$:=BSTR$(SET2)
  117.   ╞╧╥ T:=1 ╘╧ 30 ─╧
  118.     ╔╞ BINAR2$(T)="1" ╘╚┼╬
  119.       BINAR1$(T):="1"
  120.     ┼╬─╔╞
  121.   ┼╬─╞╧╥ T
  122.   ╥┼╘╒╥╬ BVAL(BINAR1$)
  123. ┼╬─╞╒╬├ UNION
  124.  
  125. ╞╒╬├ SECTION(SET1,SET2) ├╠╧╙┼─
  126.   ╔═╨╧╥╘ BSTR$,BVAL
  127.   ─╔═ BINAR1$ ╧╞ 30, BINAR2$ ╧╞ 30
  128.   BINAR1$:=BSTR$(SET1)
  129.   BINAR2$:=BSTR$(SET2)
  130.   ╞╧╥ T:=1 ╘╧ 30 ─╧
  131.     ╔╞ ╬╧╘ (BINAR1$(T)="1" ┴╬─
  132.     BINAR2$(T)="1" ╘╚┼╬
  133.       BINAR1$:="0"
  134.     ┼╬─╔╞
  135.   ┼╬─╞╧╥ T
  136.   ╥┼╘╒╥╬ BVAL(BINAR1$)
  137. ┼╬─╞╒╬├ SECTION
  138.  
  139. ╬OW:
  140.  
  141.    UNI:=UNION(SET1,SET2)
  142.    SEC:=SECTION(SET1,SET2)
  143.  
  144. ╫E CAN SHOW THE ELEMENTS OF A SET
  145. WITH
  146.  
  147. ╞╒╬├ ELEMENTS(SET) ├╠╧╙┼─
  148.   ╔═╨╧╥╘ BSTR$
  149.   ─╔═ BINAR$ ╧╞ 30
  150.   BINAR$:=BSTR$(SET)
  151.   NUM:=0 // NUMBER OF ELEMENTS
  152.   ╞╧╥ T:=1 ╘╧ 30 ─╧
  153.    ╔╞ BINAR$(T)="1" ╘╚┼╬
  154.      NUM:+1
  155.      ╨╥╔╬╘ T; // ELEMENT
  156.    ┼╬─╔╞
  157.   ┼╬─╞╧╥ T
  158.   ╨╥╔╬╘ "#",
  159.  ╥┼╘╒╥╬ NUM
  160. ┼╬─╞╒╬├ ELEMENTS
  161.  
  162. ┼XAMPLE.
  163.  
  164.    ╨╥╔╬╘ ELEMENTS(UNI)
  165.    ╨╥╔╬╘ ELEMENTS(SEC)
  166.  
  167. WITH OUTPUT
  168.  
  169.     2 3 5 6 #4
  170.     5 #1
  171.  
  172. WHERE THE NUMBER OF ELEMENTS OF THE
  173. SET IS PRINTED AFTER #.
  174.  
  175. ├REATION OF THE EMPTY SET (NO
  176. ELEMENTS) IS POSSIBLE WITH
  177.  
  178. ╞╒╬├ EMPTY ├╠╧╙┼─
  179.   ╔═╨╧╥╘ BSTR$, BVAL
  180.   // OR SIMPLY ╥┼╘╒╥╬ 0
  181.   ╥┼╘╒╥╬ BVAL(BSTR$(0))
  182. ┼╬─╞╒╬├ EMPTY
  183.  
  184. ┴ NICE EXAMPLE, SHOWING REVERSED
  185. POLISH NOTATION:
  186.  
  187. SET1:=EMPTY
  188. SET2:=EMPTY
  189. SET1:=INCLUDE(INCLUDE(INCLUDE
  190.       (SET1,3),4),5)
  191. SET2:=INCLUDE(INCLUDE(INCLUDE
  192.       (SET2,4),5),6)
  193. ╨╥╔╬╘ ELEMENTS(UNION(SECTION(SET1,
  194.       SET2),INCLUDE(SET1,7))
  195.  
  196. ┬ECAUSE A REAL NUMBER IS REPRESENTED
  197. BY 5 BYTES, THE MAXIMUM NUMBER OF
  198. ELEMENTS OF A SET IS 40 (5 TIMES 8
  199. BITS).
  200.  
  201. ╔F SETS WITH MORE THAN 40 ELEMENTS
  202. ARE WANTED, ONE CAN USE ARRAY'S.
  203. ╨RCEDURES IN STEAD OF FUNCTIONS MUST
  204. THEN BE USED.
  205.  
  206. ╔T IS ALSO POSSIBLE TO USE STRINGS
  207. LEAVING OUT THE CONVERSION INTO REAL
  208. NUMBERS.
  209.  
  210. ╔ GIVE SOME EXAMPLES IN THE FOLLWING
  211. PROGRAM:
  212.  
  213. ─╔═ A$ ╧╞ 80, B$ ╧╞ 80
  214. ─╔═ C$ ╧╞ 80, D$ ╧╞ 80
  215. A$:=EMPTY$; B$:=EMPTY$
  216. C$:=EMPTY$; D$:=EMPTY$
  217. // 4 SETS ARE NOW CREATED; EACH
  218. // WITH ROOM FOR 80 ELEMENTS
  219. //
  220. ╞╒╬├ EMPTY$ ├╠╧╙┼─
  221.   ─╔═ R$ ╧╞ 80
  222.   ╞╧╥ T:=1 ╘╧ 80 ─╧ R$:+"0"
  223.   ╥┼╘╒╥╬ R$
  224. ┼╬─╞╒╬├ EMPTY$
  225. //
  226. ╞╒╬├ INCLUDE$(SET$,ELEMENT) ├╠╧╙┼─
  227.   SET$(ELEMENT:ELEMENT):="1"
  228.   ╥┼╘╒╥╬ SET$
  229. ┼╬─╞╒╬├ INCLUDE$
  230. // USING THIS FUNCTION:
  231. //
  232. A$:=INCLUDE$(INCLUDE$(A$,3),4)
  233. B$:=INCLUDE$(INCLUDE$(B$,4),5)
  234. B$:=INCLUDE$(B$,6)
  235. //
  236. ╞╒╬├ ELEMENTS(SET$) ├╠╧╙┼─
  237.   NUM:=0
  238.   ╞╧╥ T:=1 ╘╧ 80 ─╧
  239.     ╔╞ SET$(T:T)="1" ╘╚┼╬
  240.       ╨╥╔╬╘ T;
  241.       NUM:+1
  242.     ┼╬─╔╞ 
  243.   ┼╬─╞╧╥ T
  244.   ╨╥╔╬╘ #,
  245.   ╥┼╘╒╥╬ NUM
  246. ┼╬─╞╒╬├ ELEMENTS
  247. // AND IT IS POSSIBLE TO PRINT THE
  248. // ELEMENTS:
  249. //
  250. ╨╥╔╬╘ ELEMENTS(A$)
  251. ╨╥╔╬╘ ELEMENTS(B$)
  252. //
  253. ╞╒╬├ UNION$(SET1$,SET2$) ├╠╧╙┼─
  254.   ─╔═ R$ ╧╞ 80
  255.   ╞╧╥ T:=1 ╘╧ 80 ─╧
  256.     ╔╞ SET2$(T:T)="1" ╘╚┼╬ 
  257.       SET1$(T:T):="1"
  258.     ┼╬─╔╞
  259.   ┼╬─╞╧╥ T
  260.   ╥┼╘╒╥╬ SET1$
  261. ┼╬─╞╒╬├ UNION$
  262. //
  263. C$:=UNION$(A$,B$)
  264. ╨╥╔╬╘ ELEMENTS(C$)
  265. //
  266. ╞╒╬├ SECTION$(SET1$,SET2$) ├╠╧╙┼─
  267.   ╞╧╥ T:=1 ╘╧ 80 ─╧
  268.     ╔╞ ╬╧╘ (SET1$(T:T)="1" ┴╬─
  269.     SET2$(T:T)="1") ╘╚┼╬
  270.       SET1$(T:T):="0"
  271.     ┼╬─╔╞ 
  272.   ┼╬─╞╧╥ T
  273.   ╥┼╘╒╥╬ SET1$
  274. ┼╬─╞╒╬├ SECTION$
  275. //
  276. ╨╥╔╬╘ ELEMENTS(SECTION$(A$,C$))
  277. ╨╥╔╬╘ ELEMENTS(SECTION$(B$,C$))
  278.  
  279. ╬OW THE EXECUTION OF THIS PROGRAM IS
  280. FASTER THAN FOR A PROGRAM WHICH
  281. INCLUDES CONVERSION INTO REAL
  282. NUMBERS. ┴ SECOND ADVANTAGE IS THAT
  283. THE PROGRAM IS MORE READBLE. ╚OWEVER,
  284. THERE IS MORE MEMORY OCCUPIED BY
  285. STRINGS THAN BY REAL NUMBERS.
  286.  
  287. ╔T IS LEFT TO INTERESTED READER TO
  288. CONVERT REAL FUNCTIONS SUCH AS MINUS
  289. AND SYMMINUS INTO STRING FUNCTIONS
  290. FOR SET OPERATIONS.
  291.